/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Hua YY
 * Date: 2024-12-17
 * Time: 19:13
 */
class Solution1 {
    int[] tem;
    public int[] sortArray(int[] nums) {
        //归并排序
        //传入的参数：数组，左边界，右边界
        int left = 0 , right = nums.length-1;
        tem = new int[nums.length];
        mergeSort(nums,left,right);
        return nums;
    }
    public void mergeSort(int[] nums , int left , int right){
        //1:定义出口
        if(left >= right) return;

        //2：把数组分成两个区间 [left,mid] [mid+1,right]
        int mid = (left + right)/2;

        //3:把左边区间排个序，再把右边区间排个序
        mergeSort(nums,left,mid);
        mergeSort(nums,mid+1,right);

        //4：合并排序好的两个区间
        int cur1 = left , cur2 = mid + 1 , i = 0;
        while(cur1 <= mid && cur2 <= right){
            tem[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
        }
        while(cur1 <= mid) tem[i++] = nums[cur1++];
        while(cur2 <= right) tem[i++] = nums[cur2++];

        // 5：将tem中的值copy给nums
        for(int j = left ; j <= right ; j++){
            nums[j] = tem[j-left];
        }
    }
}
public class Test1 {
    public static void main(String[] args) {
        Solution1 solution1 = new Solution1();
        int[] ret = {1,2,3,4,5};
        solution1.sortArray(ret);
    }

}
